ARC131 E - Christmas Wreath
問題
提出
やったこと
とりあえず辺の数$ M = N(N-1)/2 とする。
まず全探索で解を求めてみる。$ O(M!) なので$ N = 6 くらいが限界だが
code:brute
- R R R G B
R - R R G B
R R - G G B
R R G - G B
G G G G - B
B B B B B -
が得られた。($ i 行$ j 列が頂点$ i, j を結ぶ辺の色。問題文と色が違うが普通に間違えてた)
→なんかきれいな感じなので、きれいな感じの解が構築できそう。
三角形を構成する3辺が、行列表記でどこに並ぶか見てみると
code:edge_1-2-5
- R R R G B
R R - G G B
R R G - G B
B B B B B -
や
code:edge_2-4-6
- R R R G B
R - R R G B
R R - G G B
G G G G - B
などとと、直角三角形的な雰囲気になる。
→ それなら一つの行には$ 1 色だけ並ぶように配置すれば確実(これが公式解説のステップ1の「パターン」)
→ $ 1, 2, \dots, N を和が等しくなるよう$ 3 等分する問題になる
手動で試した感じ、$ 1 色ずつ和が$ M/3 になるように大きい方から貪欲に割り当てていけばいけそう。(未証明)
→$ N \le 50 で(自明に不可能なとき以外)全部構成成功。AC!
コード(主要部分)
code:arc131_e.py
def solve(N):
# 解
# 1, 2, ... N を 和が等しくなるよう 3 つに等分
M = N * (N - 1) // 2
if M % 3 != 0 or N < 6:
return ['No', []]
K = M // 3 # 各色の個数
COL = 'RBW' # 色の名前
for i in range(3):
left = K # 残り個数
for j in range(N-1, 0, -1): # j個の枠に入れるか
if resj != 'N': continue # j個の枠は使用済み if left >= j: # j個使えるなら使う
left -= j
if left > 0: # 割り当てしきれず(実際はここは常にFalseだった)
print('error')
return
ans = ['Yes', [resi*i for i in range(N-1, 0, -1)]] return ans
解法もっとうまく言語化したいな~